package graph;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.List;

/**
 * @Author PoX21s
 * @Date: 2021/10/29 17:50
 * @Version 1.0
 */

public class GraphDemo {
    List<String> arrayList = new ArrayList<String>();

    int[][] edge;

    int numEdges;

    boolean[] isVisited;

    public static void main(String[] args) {
        GraphDemo graphDemo = new GraphDemo(5);

        String[] vertices = {"A","B","C","D","E"};

        for (String vertex : vertices) {
            graphDemo.addVertex(vertex);
        }

        graphDemo.addEdges(0,1,1);
        graphDemo.addEdges(0,2,1);
        graphDemo.addEdges(1,2,1);
        graphDemo.addEdges(1,3,1);
        graphDemo.addEdges(1,4,1);

        graphDemo.show();

//        graphDemo.graphListDFS();
        graphDemo.graphListBFS();
    }

    public void show(){
        for (int[] ints : edge) {
            System.out.println(Arrays.toString(ints));
        }
    }

    public void addVertex(String vertex){
        arrayList.add(vertex);
    }

    public String getVertexByIndex(int i){
        return arrayList.get(i);
    }

    public GraphDemo(int n){
        edge = new int[n][n];
        isVisited = new boolean[n];
    }

    public void addEdges(int v1, int v2, int wight){
        edge[v1][v2] = wight;
        edge[v2][v1] = wight;
        numEdges++;
    }

    /*
    * 思路
    * - 找到当前节点的相邻结点
    * */
    public int getNext(int j ){
        for (int i = 0; i < arrayList.size(); i++) {
            if (edge[j][i] > 0)
                return i;
        }
        return -1;
    }

    /*
    * 思路
    * - 根据找到的相邻结点
    * */
    public int getNextByIndex(int v1, int v2){
        for (int i = v2 + 1; i < arrayList.size(); i++) {
            if (edge[v1][i] > 0 ){
                return i;
            }
        }
        return  -1;
    }

    /*
    * 思路 深度优先搜索
    * - 输出当前节点
    * - 设置当前节点已经被访问过，不在被访问
    * - 找到下一个连接节点
    * - 如果没有输出过，则输出，并遍历，找寻下一个连接结点
    *   - 如果已经输出过，则寻找当前结点的下一个连接结点，判断
    * - 重复递归判断
    * */
    private void graphListDFS(boolean[] dfs, int i){
        System.out.println(getVertexByIndex(i));
        dfs[i] = true;

        int w = getNext(i);

        while (w != -1){
            if (!dfs[w]){
                graphListDFS(dfs,w);
            }
            w = getNextByIndex(i,w);
        }
    }

    public void graphListDFS(){
        for (int i = 0; i < arrayList.size(); i++) {
            if (!isVisited[i])
                graphListDFS(isVisited,i);
        }
    }

    /*
    * 思路 广度优先搜索
    * - 输出当前结点
    * - 设置当前结点被访问过
    * - 将当前输出过的节点添加到队列中
    * - 找寻当前结点的相邻结点并输出
    *   - 移除队列中的最后
    *   - 找寻下一个当前结点连接的节点
    *       - 没有输出过则输出，并设置为被访问过
    *       - 输出过则寻找下一个当前结点的连接的节点
    *   - 将当前节点加入队列
    * - 寻找下一个当前结点连接节点，如果没有则退出循环
    * - 如果队列不为空，则继续将队列的最后一个移除并取出
    * - 循环，直到队列为空，则说明当前传入的节点的所有能够到达的节点全部输出
    * */
    public void graphListBFS(boolean[] isVisited,int i){
        int u;
        int w;
        System.out.println(getVertexByIndex(i));

        LinkedList<Integer> list = new LinkedList<>();

        isVisited[i] = true;

        list.addFirst(i);

        while (!list.isEmpty()){
            u = list.removeFirst();

            w = getNext(u);

            while (w != -1){
                if (!isVisited[w]){
                    System.out.println(getVertexByIndex(w));
                    isVisited[w] = true;
                    list.addLast(w);
                }
                w = getNextByIndex(u,w);
            }
        }
    }

    public void graphListBFS(){
        for (int i = 0; i < arrayList.size(); i++) {
            if (!isVisited[i]){
                graphListBFS(isVisited,i);
            }
        }
    }
}